﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using Data;

namespace Dijkstra
{
    // 1  function Dijkstra(Graph, source):
    // 2      for each vertex v in Graph:           // Initializations
    // 3          dist[v] := infinity               // Unknown distance function from source to v
    // 4          previous[v] := undefined          // Previous node in optimal path from source
    // 5      dist[source] := 0                     // Distance from source to source
    // 6      Q := the set of all nodes in Graph    // All nodes in the graph are unoptimized - thus are in Q
    // 7      while Q is not empty:                 // The main loop
    // 8          u := node in Q with smallest dist[]
    // 9          remove u from Q
    //10          for each neighbor v of u:         // where v has not yet been removed from Q.
    //11              alt := dist[u] + dist_between(u, v)
    //12              if alt < dist[v]              // Relax (u,v)
    //13                  dist[v] := alt
    //14                  previous[v] := u
    //15      return previous[]

    //1  S := empty sequence
    //2  u := target
    //3  while previous[u] is defined:
    //4      insert u at the beginning of S
    //5      u := previous[u]


    static public class Dijkstra
    {
        #region internal classes
        internal class Neighbour
        {
            public Guid id;
            public int distance;
        }

        internal class Node
        {
            public Guid id;
            public MapIndex location;
            public List<Neighbour> neighbours = new List<Neighbour>();
        }
        #endregion

        static public List<StarSystem> CalculateDistanceToAll(List<StarSystem> graph, Guid source, Guid target)
        {
            // Build the inital nodes of the graph
            Dictionary<Guid, Node> nodeGraph = BuildBasicNodeGraph(graph);
            Dictionary<Guid, Node> nodeSource = BuildBasicNodeGraph(graph);

            // Add inital and final locations if needed.

            // -------------------------------------------------
            // Start Dijkstra
            // -------------------------------------------------
            Dictionary<Guid, Guid> previous = Calculate(nodeGraph, source);

            //1  S := empty sequence
            //2  u := target
            //3  while previous[u] is defined:
            //4      insert u at the beginning of S
            //5      u := previous[u]
            List<StarSystem> result = new List<StarSystem>();

            Guid t = target;
            while (t != Guid.Empty)
            {
                //Guid a = previous.First(x => x.Key == t).Value;
                result.Add(graph.Find(ss => ss.GetWarpPoint(t) != null));
                t = previous[t];
            }

            return result;
        }

        internal static Dictionary<Guid, Guid> Calculate(Dictionary<Guid, Node> nodeGraph, Guid source)
        {
            Dictionary<Guid, int> distance = new Dictionary<Guid, int>();
            Dictionary<Guid, Guid> previous = new Dictionary<Guid, Guid>();

            foreach (KeyValuePair<Guid, Node> node in nodeGraph)
            {
                distance[node.Value.id] = int.MaxValue;
                previous[node.Value.id] = Guid.Empty;
            }

            distance[source] = 0;

            // 7 while Q is not empty:                 // The main loop
            while (nodeGraph.Count() != 0)
            {
                // 8 u := node in Q with smallest dist[]
                int d = distance.Min(dist => dist.Value);
                Guid smallest = distance.First(dist => dist.Value == d).Key;
                Node u = nodeGraph[smallest];

                // 9 remove u from Q
                nodeGraph.Remove(smallest);

                //10 for each neighbor v of u:         // where v has not yet been removed from Q.
                foreach (Neighbour v in u.neighbours)
                {
                    if (!distance.ContainsKey(v.id))
                        continue;

                    //11 alt := dist[u] + dist_between(u, v)
                    int alt = distance[u.id] + v.distance;

                    //12 if alt < dist[v]              // Relax (u,v)
                    if (alt < distance[v.id])
                    {
                        //13 dist[v] := alt
                        distance[v.id] = alt;

                        //14 previous[v] := u
                        previous[v.id] = u.id;
                    }
                }

                distance.Remove(smallest);
            }

            return previous;
        }

        #region internal methods
        internal static Dictionary<Guid, Node> SystemNodes(StarSystem star)
        {
            Dictionary<Guid, Node> systemNodes = new Dictionary<Guid, Node>();

            foreach (MasterWarpPoint wp in star.MasterWpList().Values)
            {
                Node node = new Node();
                node.id = wp.WarpPointId;
                node.location = wp.Location;

                foreach (MasterWarpPoint neighbour in star.MasterWpList().Values)
                {
                    if (neighbour.WarpPointId != wp.WarpPointId)
                    {
                        Neighbour n = new Neighbour();
                        n.id = neighbour.WarpPointId;
                        n.distance = Universe.RangeTo( wp.Location, neighbour.Location);

                        node.neighbours.Add(n);
                    }
                }

                systemNodes.Add(node.id, node);
            }

            return systemNodes;
        }

        internal static void LinkSystems(StarSystem star, Dictionary<Guid, Node> nodeGraph)
        {
            foreach (MasterWarpPoint wp in star.MasterWpList().Values)
            {
                // locate the other side
                StarSystem dest = Universe.GetStarSystem(wp.DestinationId);

                // locate the start node
                Node startNode = null;
                foreach (KeyValuePair<Guid, Node> n in nodeGraph)
                {
                    if (n.Value.id == wp.WarpPointId)
                    {
                        startNode = n.Value;
                        break;
                    }
                }

                // locate the other node
                Node endNode = null;
                foreach (MasterWarpPoint neighbour in dest.MasterWpList().Values)
                {
                    if (neighbour.DestinationId == star.StarId)
                    {
                        foreach (KeyValuePair<Guid, Node> n in nodeGraph)
                        {
                            if (n.Value.id == neighbour.WarpPointId)
                            {
                                endNode = n.Value;
                                break;
                            }
                        }
                    }
                    if (endNode != null)
                        break;
                }
                
                // Update startNode              
                Neighbour nNeighbour = new Neighbour();
                nNeighbour.id = endNode.id;
                nNeighbour.distance = 0;

                startNode.neighbours.Add(nNeighbour);
            }
        }

        internal static Dictionary<Guid, Node> BuildBasicNodeGraph(List<StarSystem> graph)
        {
            Dictionary<Guid, Node> nodeGraph = new Dictionary<Guid, Node>();

            // Build the inital nodes of the graph
            foreach (StarSystem star in graph)
            {
                Dictionary<Guid, Node> temp = SystemNodes(star);

                foreach (KeyValuePair<Guid, Node> node in temp)
                    nodeGraph.Add(node.Key, node.Value);
            }

            // Link the external system nodes
            foreach (StarSystem star in graph)
                LinkSystems(star, nodeGraph);

            return nodeGraph;
        }
        #endregion
    }
}
